package cn.rocky.prepare;

import java.util.Arrays;

public class findLongestChain {

    // [[1,2],[2,3],[3,4]]
    public int findLongestChain(int[][] pairs) {
        int count = 1;
        int length = pairs.length;
        if (length == 1) {return  count;}
        Arrays.sort(pairs,(o1,o2) -> Integer.compare(o1[0],o2[0]));
        for (int i = 1; i < length; i++) {
            if (pairs[i][0] > pairs[i - 1][1]) {
                count++;
            } else {
                pairs[i][1] = Math.min(pairs[i][1],pairs[i - 1][1]);
            }
        }
        return count;
    }

    public int findLongestChain1(int[][] pairs) {
        int curr = Integer.MIN_VALUE, res = 0;
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
        for (int[] p : pairs) {
            if (curr < p[0]) {
                curr = p[1];
                res++;
            }
        }
        return res;
    }
}
